/**
 * @ClassName Offer26
 * @Description 剑指 Offer 26. 树的子结构
 * @Author clockTown
 * @Date 2021/8/18 8:08
 * @Version 1.0
 */
class Offer26 {
}

class Offer26V0 {

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }

    boolean recur(TreeNode A, TreeNode B) {
        // 如果B为null, 说明树 B 已匹配完成（越过叶子节点），因此返回 true
        if (B == null) {
            return true;
        }
        // 当节点 A 为空：说明已经越过树 A 叶子节点，即匹配失败，返回 false
        // 当节点 A 和 B 的值不同：说明匹配失败，返回 false
        if (A == null || A.val != B.val) {
            return false;
        }
        return recur(A.left, B.left) && recur(A.right, B.right);
    }
}